package dataStructure.study.sort;

/**
 * Author: shangsf
 * Date: 2021/4/6 22:36
 * Description:插入排序，时间复杂度O(n^2)
 */
public class InsertionSort {

    /**
     * 数组
     * @param array
     */
    public static void sort(int[] array){
        if(array==null||array.length==1){
            return;
        }
        int n=array.length;
        for(int i=1;i<n;i++){
            int value=array[i];
            int j=i-1;
            for(;j>=0;j--){
                if(array[j]>value){
                    array[j+1]=array[j];
                }else {
                    break;
                }
            }
            array[j+1]=value;
        }
    }

    /**
     * 链表
     * @param head
     * @return
     */
    public static ListNode sort(ListNode head) {
        if(head==null){
            return head;
        }
        ListNode hean1=new ListNode(head.val);

        ListNode node1=head.next;
        while(node1!=null){
            ListNode tmp=node1;
            node1=node1.next;

            ListNode prv=null;
            ListNode node2=hean1;
            boolean change=false;
            while(node2!=null){
                if(node2.val>tmp.val){
                    if(prv==null){
                        hean1=tmp;
                        tmp.next=node2;
                    }else{
                        prv.next=tmp;
                        tmp.next=node2;
                    }
                    change=true;
                    break;
                }
                prv=node2;
                node2=node2.next;
            }
            if(change==false){
                ListNode tmp1=new ListNode(tmp.val);
                prv.next=tmp1;
            }
        }
        return hean1;
    }

    public static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
}
